/*
 * ltree的操作函数
 * Teodor Sigaev <teodor@stack.net>
 * contrib/ltree/ltree_op.c
 */
#include "postgres.h"

#include <ctype.h>

#include "access/htup_details.h"
#include "catalog/pg_statistic.h"
#include "ltree.h"
#include "utils/builtins.h"
#include "utils/lsyscache.h"
#include "utils/selfuncs.h"

PG_MODULE_MAGIC;

/* 比较函数 */
PG_FUNCTION_INFO_V1(ltree_cmp);
PG_FUNCTION_INFO_V1(ltree_lt);
PG_FUNCTION_INFO_V1(ltree_le);
PG_FUNCTION_INFO_V1(ltree_eq);
PG_FUNCTION_INFO_V1(ltree_ne);
PG_FUNCTION_INFO_V1(ltree_ge);
PG_FUNCTION_INFO_V1(ltree_gt);
PG_FUNCTION_INFO_V1(nlevel);
PG_FUNCTION_INFO_V1(ltree_isparent);
PG_FUNCTION_INFO_V1(ltree_risparent);
PG_FUNCTION_INFO_V1(subltree);
PG_FUNCTION_INFO_V1(subpath);
PG_FUNCTION_INFO_V1(ltree_index);
PG_FUNCTION_INFO_V1(ltree_addltree);
PG_FUNCTION_INFO_V1(ltree_addtext);
PG_FUNCTION_INFO_V1(ltree_textadd);
PG_FUNCTION_INFO_V1(lca);
PG_FUNCTION_INFO_V1(ltree2text);
PG_FUNCTION_INFO_V1(text2ltree);
PG_FUNCTION_INFO_V1(ltreeparentsel);

int ltree_compare(const ltree *fc_a, const ltree *fc_b)
{
	ltree_level *fc_al = LTREE_FIRST(fc_a);
	ltree_level *fc_bl = LTREE_FIRST(fc_b);
	int			fc_an = fc_a->numlevel;
	int			fc_bn = fc_b->numlevel;

	while (fc_an > 0 && fc_bn > 0)
	{
		int			fc_res;

		if ((fc_res = memcmp(fc_al->name, fc_bl->name, Min(fc_al->len, fc_bl->len))) == 0)
		{
			if (fc_al->len != fc_bl->len)
				return (fc_al->len - fc_bl->len) * 10 * (fc_an + 1);
		}
		else
		{
			if (fc_res < 0)
				fc_res = -1;
			else
				fc_res = 1;
			return fc_res * 10 * (fc_an + 1);
		}

		fc_an--;
		fc_bn--;
		fc_al = LEVEL_NEXT(fc_al);
		fc_bl = LEVEL_NEXT(fc_bl);
	}

	return (fc_a->numlevel - fc_b->numlevel) * 10 * (fc_an + 1);
}

#define RUNCMP						\
ltree *fc_a = PG_GETARG_LTREE_P(0);	\
ltree *fc_b = PG_GETARG_LTREE_P(1);	\
int fc_res = ltree_compare(fc_a,fc_b);		\
PG_FREE_IF_COPY(fc_a,0);				\
PG_FREE_IF_COPY(fc_b,1)

Datum ltree_cmp(PG_FUNCTION_ARGS)
{
	RUNCMP;
	PG_RETURN_INT32(fc_res);
}

Datum ltree_lt(PG_FUNCTION_ARGS)
{
	RUNCMP;
	PG_RETURN_BOOL(fc_res < 0);
}

Datum ltree_le(PG_FUNCTION_ARGS)
{
	RUNCMP;
	PG_RETURN_BOOL(fc_res <= 0);
}

Datum ltree_eq(PG_FUNCTION_ARGS)
{
	RUNCMP;
	PG_RETURN_BOOL(fc_res == 0);
}

Datum ltree_ge(PG_FUNCTION_ARGS)
{
	RUNCMP;
	PG_RETURN_BOOL(fc_res >= 0);
}

Datum ltree_gt(PG_FUNCTION_ARGS)
{
	RUNCMP;
	PG_RETURN_BOOL(fc_res > 0);
}

Datum ltree_ne(PG_FUNCTION_ARGS)
{
	RUNCMP;
	PG_RETURN_BOOL(fc_res != 0);
}

Datum nlevel(PG_FUNCTION_ARGS)
{
	ltree	   *fc_a = PG_GETARG_LTREE_P(0);
	int			fc_res = fc_a->numlevel;

	PG_FREE_IF_COPY(fc_a, 0);
	PG_RETURN_INT32(fc_res);
}

bool inner_isparent(const ltree *fc_c, const ltree *fc_p)
{
	ltree_level *fc_cl = LTREE_FIRST(fc_c);
	ltree_level *fc_pl = LTREE_FIRST(fc_p);
	int			fc_pn = fc_p->numlevel;

	if (fc_pn > fc_c->numlevel)
		return false;

	while (fc_pn > 0)
	{
		if (fc_cl->len != fc_pl->len)
			return false;
		if (memcmp(fc_cl->name, fc_pl->name, fc_cl->len) != 0)
			return false;

		fc_pn--;
		fc_cl = LEVEL_NEXT(fc_cl);
		fc_pl = LEVEL_NEXT(fc_pl);
	}
	return true;
}

Datum ltree_isparent(PG_FUNCTION_ARGS)
{
	ltree	   *fc_c = PG_GETARG_LTREE_P(1);
	ltree	   *fc_p = PG_GETARG_LTREE_P(0);
	bool		fc_res = inner_isparent(fc_c, fc_p);

	PG_FREE_IF_COPY(fc_c, 1);
	PG_FREE_IF_COPY(fc_p, 0);
	PG_RETURN_BOOL(fc_res);
}

Datum ltree_risparent(PG_FUNCTION_ARGS)
{
	ltree	   *fc_c = PG_GETARG_LTREE_P(0);
	ltree	   *fc_p = PG_GETARG_LTREE_P(1);
	bool		fc_res = inner_isparent(fc_c, fc_p);

	PG_FREE_IF_COPY(fc_c, 0);
	PG_FREE_IF_COPY(fc_p, 1);
	PG_RETURN_BOOL(fc_res);
}


static ltree * fc_inner_subltree(ltree *fc_t, int32 fc_startpos, int32 fc_endpos)
{
	char	   *fc_start = NULL,
			   *fc_end = NULL;
	ltree_level *fc_ptr = LTREE_FIRST(fc_t);
	ltree	   *fc_res;
	int			fc_i;

	if (fc_startpos < 0 || fc_endpos < 0 || fc_startpos >= fc_t->numlevel || fc_startpos > fc_endpos)
		ereport(ERROR,
				(errcode(ERRCODE_INVALID_PARAMETER_VALUE),
				 errmsg("invalid positions")));

	if (fc_endpos > fc_t->numlevel)
		fc_endpos = fc_t->numlevel;

	fc_start = fc_end = (char *) fc_ptr;
	for (fc_i = 0; fc_i < fc_endpos; fc_i++)
	{
		if (fc_i == fc_startpos)
			fc_start = (char *) fc_ptr;
		if (fc_i == fc_endpos - 1)
		{
			fc_end = (char *) LEVEL_NEXT(fc_ptr);
			break;
		}
		fc_ptr = LEVEL_NEXT(fc_ptr);
	}

	fc_res = (ltree *) palloc0(LTREE_HDRSIZE + (fc_end - fc_start));
	SET_VARSIZE(fc_res, LTREE_HDRSIZE + (fc_end - fc_start));
	fc_res->numlevel = fc_endpos - fc_startpos;

	memcpy(LTREE_FIRST(fc_res), fc_start, fc_end - fc_start);

	return fc_res;
}

Datum subltree(PG_FUNCTION_ARGS)
{
	ltree	   *fc_t = PG_GETARG_LTREE_P(0);
	ltree	   *fc_res = fc_inner_subltree(fc_t, PG_GETARG_INT32(1), PG_GETARG_INT32(2));

	PG_FREE_IF_COPY(fc_t, 0);
	PG_RETURN_POINTER(fc_res);
}

Datum subpath(PG_FUNCTION_ARGS)
{
	ltree	   *fc_t = PG_GETARG_LTREE_P(0);
	int32		fc_start = PG_GETARG_INT32(1);
	int32		fc_len = (fcinfo->nargs == 3) ? PG_GETARG_INT32(2) : 0;
	int32		fc_end;
	ltree	   *fc_res;

	fc_end = fc_start + fc_len;

	if (fc_start < 0)
	{
		fc_start = fc_t->numlevel + fc_start;
		fc_end = fc_start + fc_len;
	}
	if (fc_start < 0)
	{							/* start > t->numlevel */
		fc_start = fc_t->numlevel + fc_start;
		fc_end = fc_start + fc_len;
	}

	if (fc_len < 0)
		fc_end = fc_t->numlevel + fc_len;
	else if (fc_len == 0)
		fc_end = (fcinfo->nargs == 3) ? fc_start : 0xffff;

	fc_res = fc_inner_subltree(fc_t, fc_start, fc_end);

	PG_FREE_IF_COPY(fc_t, 0);
	PG_RETURN_POINTER(fc_res);
}

static ltree * fc_ltree_concat(ltree *fc_a, ltree *fc_b)
{
	ltree	   *fc_r;
	int			fc_numlevel = (int) fc_a->numlevel + fc_b->numlevel;

	if (fc_numlevel > LTREE_MAX_LEVELS)
		ereport(ERROR,
				(errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
				 errmsg("number of ltree levels (%d) exceeds the maximum allowed (%d)",
						fc_numlevel, LTREE_MAX_LEVELS)));

	fc_r = (ltree *) palloc0(VARSIZE(fc_a) + VARSIZE(fc_b) - LTREE_HDRSIZE);
	SET_VARSIZE(fc_r, VARSIZE(fc_a) + VARSIZE(fc_b) - LTREE_HDRSIZE);
	fc_r->numlevel = (uint16) fc_numlevel;

	memcpy(LTREE_FIRST(fc_r), LTREE_FIRST(fc_a), VARSIZE(fc_a) - LTREE_HDRSIZE);
	memcpy(((char *) LTREE_FIRST(fc_r)) + VARSIZE(fc_a) - LTREE_HDRSIZE,
		   LTREE_FIRST(fc_b),
		   VARSIZE(fc_b) - LTREE_HDRSIZE);
	return fc_r;
}

Datum ltree_addltree(PG_FUNCTION_ARGS)
{
	ltree	   *fc_a = PG_GETARG_LTREE_P(0);
	ltree	   *fc_b = PG_GETARG_LTREE_P(1);
	ltree	   *fc_r;

	fc_r = fc_ltree_concat(fc_a, fc_b);
	PG_FREE_IF_COPY(fc_a, 0);
	PG_FREE_IF_COPY(fc_b, 1);
	PG_RETURN_POINTER(fc_r);
}

Datum ltree_addtext(PG_FUNCTION_ARGS)
{
	ltree	   *fc_a = PG_GETARG_LTREE_P(0);
	text	   *fc_b = PG_GETARG_TEXT_PP(1);
	char	   *fc_s;
	ltree	   *fc_r,
			   *fc_tmp;

	fc_s = text_to_cstring(fc_b);

	fc_tmp = (ltree *) DatumGetPointer(DirectFunctionCall1(ltree_in,
														PointerGetDatum(fc_s)));

	pfree(fc_s);

	fc_r = fc_ltree_concat(fc_a, fc_tmp);

	pfree(fc_tmp);

	PG_FREE_IF_COPY(fc_a, 0);
	PG_FREE_IF_COPY(fc_b, 1);
	PG_RETURN_POINTER(fc_r);
}

Datum ltree_index(PG_FUNCTION_ARGS)
{
	ltree	   *fc_a = PG_GETARG_LTREE_P(0);
	ltree	   *fc_b = PG_GETARG_LTREE_P(1);
	int			fc_start = (fcinfo->nargs == 3) ? PG_GETARG_INT32(2) : 0;
	int			fc_i,
				fc_j;
	ltree_level *fc_startptr,
			   *fc_aptr,
			   *fc_bptr;
	bool		fc_found = false;

	if (fc_start < 0)
	{
		if (-fc_start >= fc_a->numlevel)
			fc_start = 0;
		else
			fc_start = (int) (fc_a->numlevel) + fc_start;
	}

	if (fc_a->numlevel - fc_start < fc_b->numlevel || fc_a->numlevel == 0 || fc_b->numlevel == 0)
	{
		PG_FREE_IF_COPY(fc_a, 0);
		PG_FREE_IF_COPY(fc_b, 1);
		PG_RETURN_INT32(-1);
	}

	fc_startptr = LTREE_FIRST(fc_a);
	for (fc_i = 0; fc_i <= fc_a->numlevel - fc_b->numlevel; fc_i++)
	{
		if (fc_i >= fc_start)
		{
			fc_aptr = fc_startptr;
			fc_bptr = LTREE_FIRST(fc_b);
			for (fc_j = 0; fc_j < fc_b->numlevel; fc_j++)
			{
				if (!(fc_aptr->len == fc_bptr->len && memcmp(fc_aptr->name, fc_bptr->name, fc_aptr->len) == 0))
					break;
				fc_aptr = LEVEL_NEXT(fc_aptr);
				fc_bptr = LEVEL_NEXT(fc_bptr);
			}

			if (fc_j == fc_b->numlevel)
			{
				fc_found = true;
				break;
			}
		}
		fc_startptr = LEVEL_NEXT(fc_startptr);
	}

	if (!fc_found)
		fc_i = -1;

	PG_FREE_IF_COPY(fc_a, 0);
	PG_FREE_IF_COPY(fc_b, 1);
	PG_RETURN_INT32(fc_i);
}

Datum ltree_textadd(PG_FUNCTION_ARGS)
{
	ltree	   *fc_a = PG_GETARG_LTREE_P(1);
	text	   *fc_b = PG_GETARG_TEXT_PP(0);
	char	   *fc_s;
	ltree	   *fc_r,
			   *fc_tmp;

	fc_s = text_to_cstring(fc_b);

	fc_tmp = (ltree *) DatumGetPointer(DirectFunctionCall1(ltree_in,
														PointerGetDatum(fc_s)));

	pfree(fc_s);

	fc_r = fc_ltree_concat(fc_tmp, fc_a);

	pfree(fc_tmp);

	PG_FREE_IF_COPY(fc_a, 1);
	PG_FREE_IF_COPY(fc_b, 0);
	PG_RETURN_POINTER(fc_r);
}

/*
 * lca()变体的通用代码，查找输入的最长公共祖先
 *
 * 如果没有公共祖先，则返回NULL，即最长公共前缀为空。
 */
ltree *
lca_inner(ltree **fc_a, int fc_len)
{
	int			fc_tmp,
				fc_num,
				fc_i,
				fc_reslen;
	ltree	  **fc_ptr;
	ltree_level *fc_l1,
			   *fc_l2;
	ltree	   *fc_res;

	if (fc_len <= 0)
		return NULL;			/* 没有输入？ */
	if ((*fc_a)->numlevel == 0)
		return NULL;			/* 任何空输入意味着结果为NULL */

	/* num是迄今为止最长公共祖先的长度 */
	fc_num = (*fc_a)->numlevel - 1;

	/* 将每个额外输入与*a进行比较 */
	fc_ptr = fc_a + 1;
	while (fc_ptr - fc_a < fc_len)
	{
		if ((*fc_ptr)->numlevel == 0)
			return NULL;
		else if ((*fc_ptr)->numlevel == 1)
			fc_num = 0;
		else
		{
			fc_l1 = LTREE_FIRST(*fc_a);
			fc_l2 = LTREE_FIRST(*fc_ptr);
			fc_tmp = Min(fc_num, (*fc_ptr)->numlevel - 1);
			fc_num = 0;
			for (fc_i = 0; fc_i < fc_tmp; fc_i++)
			{
				if (fc_l1->len == fc_l2->len &&
					memcmp(fc_l1->name, fc_l2->name, fc_l1->len) == 0)
					fc_num = fc_i + 1;
				else
					break;
				fc_l1 = LEVEL_NEXT(fc_l1);
				fc_l2 = LEVEL_NEXT(fc_l2);
			}
		}
		fc_ptr++;
	}

	/* 现在计算结果的大小... */
	fc_reslen = LTREE_HDRSIZE;
	fc_l1 = LTREE_FIRST(*fc_a);
	for (fc_i = 0; fc_i < fc_num; fc_i++)
	{
		fc_reslen += MAXALIGN(fc_l1->len + LEVEL_HDRSIZE);
		fc_l1 = LEVEL_NEXT(fc_l1);
	}

	/* ...并通过复制*a来构造它 */
	fc_res = (ltree *) palloc0(fc_reslen);
	SET_VARSIZE(fc_res, fc_reslen);
	fc_res->numlevel = fc_num;

	fc_l1 = LTREE_FIRST(*fc_a);
	fc_l2 = LTREE_FIRST(fc_res);

	for (fc_i = 0; fc_i < fc_num; fc_i++)
	{
		memcpy(fc_l2, fc_l1, MAXALIGN(fc_l1->len + LEVEL_HDRSIZE));
		fc_l1 = LEVEL_NEXT(fc_l1);
		fc_l2 = LEVEL_NEXT(fc_l2);
	}

	return fc_res;
}

Datum lca(PG_FUNCTION_ARGS)
{
	int			fc_i;
	ltree	  **fc_a,
			   *fc_res;

	fc_a = (ltree **) palloc(sizeof(ltree *) * fcinfo->nargs);
	for (fc_i = 0; fc_i < fcinfo->nargs; fc_i++)
		fc_a[fc_i] = PG_GETARG_LTREE_P(fc_i);
	fc_res = lca_inner(fc_a, (int) fcinfo->nargs);
	for (fc_i = 0; fc_i < fcinfo->nargs; fc_i++)
		PG_FREE_IF_COPY(fc_a[fc_i], fc_i);
	pfree(fc_a);

	if (fc_res)
		PG_RETURN_POINTER(fc_res);
	else
		PG_RETURN_NULL();
}

Datum text2ltree(PG_FUNCTION_ARGS)
{
	text	   *fc_in = PG_GETARG_TEXT_PP(0);
	char	   *fc_s;
	ltree	   *fc_out;

	fc_s = text_to_cstring(fc_in);

	fc_out = (ltree *) DatumGetPointer(DirectFunctionCall1(ltree_in,
														PointerGetDatum(fc_s)));
	pfree(fc_s);
	PG_FREE_IF_COPY(fc_in, 0);
	PG_RETURN_POINTER(fc_out);
}


Datum ltree2text(PG_FUNCTION_ARGS)
{
	ltree	   *fc_in = PG_GETARG_LTREE_P(0);
	char	   *fc_ptr;
	int			fc_i;
	ltree_level *fc_curlevel;
	text	   *fc_out;

	fc_out = (text *) palloc(VARSIZE(fc_in) + VARHDRSZ);
	fc_ptr = VARDATA(fc_out);
	fc_curlevel = LTREE_FIRST(fc_in);
	for (fc_i = 0; fc_i < fc_in->numlevel; fc_i++)
	{
		if (fc_i != 0)
		{
			*fc_ptr = '.';
			fc_ptr++;
		}
		memcpy(fc_ptr, fc_curlevel->name, fc_curlevel->len);
		fc_ptr += fc_curlevel->len;
		fc_curlevel = LEVEL_NEXT(fc_curlevel);
	}

	SET_VARSIZE(fc_out, fc_ptr - ((char *) fc_out));
	PG_FREE_IF_COPY(fc_in, 0);

	PG_RETURN_POINTER(fc_out);
}


/*
 *	ltreeparentsel - ltree数据类型的父关系选择性。
 *
 * 如果ltree扩展已更新到1.2或更高版本，则不再使用此函数。
 */
Datum ltreeparentsel(PG_FUNCTION_ARGS)
{
	PlannerInfo *fc_root = (PlannerInfo *) PG_GETARG_POINTER(0);
	Oid			fc_operator = PG_GETARG_OID(1);
	List	   *fc_args = (List *) PG_GETARG_POINTER(2);
	int			fc_varRelid = PG_GETARG_INT32(3);
	double		fc_selec;

	/* 使用通用限制选择性逻辑，默认值为0.001。 */
	fc_selec = generic_restriction_selectivity(fc_root, fc_operator, InvalidOid,
											fc_args, fc_varRelid,
											0.001);

	PG_RETURN_FLOAT8((float8) fc_selec);
}
